The Internet address space is a set of globally (world-wide) unique numbers. Addresses are assigned to various networks, to ensure that no two networks attempt to use the same network address in the Internet. The address assignment is provided by a registration service referred to as Regional Internet Registries that track IP address allocation. Users normally refer to specific computing devices and services on the internet using “names,” (e.g., www.microsoft.com) as opposed to numbers. But when computers make network connections these names are immediately translated to numeric IP addresses, which are used in connecting to the desired computing device or service.
The traditional numeric IP address (also called IPv4, standing for IP version 4) is a 32-bit number that uniquely identifies a network interface on a host. A host typically has one network interface and consequently one IP address, although sometimes it is equipped with multiple network interfaces. Because of the 32-bit limitation, the IPv4 address space is capable of addressing a theoretical maximum of 4,294,967,296 (232) distinct IP numbers (hosts). The IP addresses are commonly written in “dot notation”, as four decimal numbers, separated by dots, e.g. 209.92.56.2. Each number can have a maximum value of 255. Hence, IP address space is from 0.0.0.0 to 255.255.255.255.
The IP has the addressing structure, which developed as a two-level hierarchy in both addressing and routing. One part of the address, the network part, identifies the particular network a host is connected to, while the other part, the local part, identifies the particular end host on that network. Internet routing, then, has to deal only with the network part of the address, routing the packet to a router directly connected to the destination network. The local part is not used at all in Internet routing itself; rather it is used to determine the intended host on the destination network. An organization can use some of the bits in the host part of the address to identify a specific subnet. Effectively, the IP address then contains three parts: the network number, the subnet number, and the machine number.
IP addresses can be one of several classes, each determining how many bits represent the network number and how many represent the host number. The most common class used by large organizations (Class B) allows 16 bits for the network number and 16 for the host number. Using the above example, here's how the IP address is divided:
  <            --      Network        ⁢                  ⁢          address      --        >  <            --      Host        ⁢                  ⁢          address      --        >          ⁢          ⁢      209.92    ⁢                  .                  ⁢    56.2  To add subnetting to this address, some portion (in this example, eight bits) of the host address could be used for a subnet address. Thus:
      <                  --        Network            ⁢                          ⁢              address        --              >    <                  --        Subnet            ⁢                          ⁢              address        --              >    <                  --        Host            ⁢                          ⁢              address        --              >                  ⁢                  ⁢          209.92      ⁢                          .                          ⁢      56      ⁢                          .                          ⁢      2        ⁢        In other words, the subnet is divided into eight bits but an organization could choose some other scheme using only part of the third quad or even part of the fourth quad.
A subnet (short for “subnetwork”) is an identifiably separate part of an organization's network. Typically, a subnet may represent all the machines at one geographic location, in one building, or on the same local area network (LAN). Having an organization's network divided into subnets allows it to be connected to the Internet with a single shared network address. Without subnets, an organization could get multiple connections to the Internet, one for each of its physically separate subnetworks, but this would require an unnecessary use of the limited number of network numbers the Internet has to assign. It would also require that Internet routing tables on gateways outside the organization would need to know about and have to manage routing that could and should be handled within an organization.
The ubiquity of the Internet has spawned a variety of attacks that attempt to provide a payload of malicious code to a significant percentage of computing devices connected to the Internet. Because of the number of computing devices connected to the Internet (e.g., 232 for IPv4 and 264 for IPv6) propagation of the payload is an obstacle to the spread of the malicious code during an attack. Several propagation algorithms have surfaced that provide for rapid propagation. For example, a typical propagation technique scans through the IP address space sequentially, i.e., starting at 0.0.0.0 and ending at 255.255.255.255. The scanning program usually looks for active network connected computing devices by sending a message to an arbitrary IP address and listening for a response.
Typically, scanning is done by dividing the IP address space of interest (e.g., the entire IPv4 address space) among a number of computing devices, each of which will start at the beginning of its assigned IP address space and scan for a computing device that responds to an inquiry. After a connected, responsive computing device is found, that computing device will be provided with a payload. The payload usually enlists the newly infected computing device to join the scanning within an assigned address space, which is a subset of the address space assigned to the infecting machine.
Some such scanning techniques use a form of a binary tree. With each computing device, dividing its assigned address space into two parts. Each part is scanned until a computing device is found and provided with the payload. The newly infected machines repeat the process until the entire IP address space has been scanned.
Other techniques for propagating address space employ a hit list. Using such that techniques, a block of address space is forwarded to a computing device, which then divides the hit list and passes portions on to found computing devices. This allows a complete randomization of the address space, but also requires a large file to be transmitted over the network.
The subject invention addresses the drawbacks of the scanning and hit list techniques for propagating a payload through a network.